/* 空闲链表+最佳适应法 indefinite time 不建议实时任务使用 */
/* 头尾双哨兵节点，双链结构 */

#include "heap.h"
#include <stdint.h>
#define configHEAPSIZE (4*1024)
#define ROUND_UP(X) (((X) + sizeof(size_t) - 1) & (~(sizeof(size_t) - 1)))
#define BLOCK_OFFSET(BlcokSize) ((BlcokSize) + sizeof(Node_t))

typedef struct Node_t Node_t;

struct Node_t
{
    size_t size;
    Node_t *next;
    Node_t *pre;
};

static _Alignas(size_t) uint8_t Heap[configHEAPSIZE];
static Node_t headNode;
static Node_t endNode;

void* cMalloc(size_t wantedSize)
{
    if (wantedSize == 0)
        return NULL;

    wantedSize = ROUND_UP(wantedSize);

    /* endNode or IdleBlock */
    Node_t *pCurNode = headNode.next;

    Node_t *pBestBlockNode = NULL;
    size_t bestDiff = SIZE_MAX;
    /* 最佳适应法，找到最适合的空闲区域，遍历整个链表 */
    /* 先处理 First Best Block */
    while (pCurNode->next != NULL)
    {
        if (pCurNode->size >= wantedSize)
        {
            uint32_t thisDiff = pCurNode->size - wantedSize;
            if (bestDiff > thisDiff)
            {
                bestDiff = thisDiff;
                pBestBlockNode = pCurNode;
            }
        }
        pCurNode = pCurNode->next;
    }

    /* pBestBlockNode = NULL or IdleBlock */
    if (pBestBlockNode == NULL)
        return NULL;

    /* pBestBlockNode = IdleBlock */
    // 空闲块分割
    if (pBestBlockNode->size >= BLOCK_OFFSET(wantedSize) + sizeof(size_t))
    {
        Node_t *leftBlockNode = (Node_t*)((void*)pBestBlockNode + BLOCK_OFFSET(wantedSize));
        leftBlockNode->size = pBestBlockNode->size - wantedSize - sizeof(Node_t);
        leftBlockNode->next = pBestBlockNode->next;

        pCurNode = leftBlockNode;

        /* 分配空间 */
        pBestBlockNode->size = wantedSize;
    }
    else
    {
        pCurNode = pBestBlockNode->next;
    }
    /* pCurNode = leftBlockNode or pBestBlockNode->next */
    /* 将pCurNode插入到pBestBlockNode前 */
    pBestBlockNode->pre->next = pCurNode;
    pCurNode->pre = pBestBlockNode->pre;

    return ((void*)pBestBlockNode) + sizeof(Node_t);
}

void cFree(void* pBlock)
{
    Node_t *pNode = (Node_t*)((void*)pBlock - sizeof(Node_t));

    /* 遍历空闲列表 */
    Node_t *pRightNode = headNode.next;
    Node_t *pLeftNode;

    /* 找到 释放的块 在空闲链表中的位置 */
    while ((pRightNode->next != NULL) && (pNode > pRightNode))
    {
        pRightNode = pRightNode->next;
    }
    /* pRightNode 为空闲节点或尾节点 插入位置在pRightNode左侧 */

    /* 记录左侧节点 */
    pLeftNode = pRightNode->pre;
    /* pLeftNode & pRightNode */

    /* 记录释放节点左侧节点的边界 */
    Node_t *LeftNode_EndLimit = (Node_t*)((void*)pLeftNode + BLOCK_OFFSET(pLeftNode->size));
    /* 记录释放节点的边界 */
    Node_t *block_EndLimit = (Node_t*)((void*)pNode + BLOCK_OFFSET(pNode->size));

    /* 前合并 */
    if ((pLeftNode->pre != NULL) && (LeftNode_EndLimit == pNode))
    {
        pLeftNode->size += BLOCK_OFFSET(pNode->size);
        pNode = pLeftNode;
    }
    else
    {
        pLeftNode->next = pNode;
        pNode->pre = pLeftNode;
    }


    /* 后合并 */
    if ((pRightNode->next != NULL) && (block_EndLimit == pRightNode))
    {
        pNode->size += BLOCK_OFFSET(pRightNode->size);
        pNode->next = pRightNode->next;
        pRightNode->next->pre = pNode;
    }
    else
    {
        pNode->next = pRightNode;
        pRightNode->pre = pNode;
    }
    
    return;
}

void HeapInit(void)
{
    /* 初始化堆 */
    headNode.size = 0;
    headNode.next = (Node_t*)&Heap;
    headNode.pre = NULL;

    headNode.next->size = configHEAPSIZE - sizeof(Node_t);
    headNode.next->next = &endNode;
    headNode.next->pre = &headNode;

    endNode.size = 0;
    endNode.next = NULL;
    endNode.pre = headNode.next;
}

/*------------------------------------------------------------------*/
#include <stdio.h>
void printIdleBlocks(void)
{
    Node_t *node = headNode.next;
    int index = 0;

    while (node->next)
    {
        printf("-----------\n");
        printf("index = %d \n", index++);
        printf("Size  = %d \n", node->size);
        node = node->next;
    }
}